


<!doctype html>
<html lang="zh" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      
      
      
      <link rel="shortcut icon" href="../../assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.1, mkdocs-material-5.1.4">
    
    
      
        <title>实验概述 - 操作系统（2020秋季） | 哈工大（深圳）</title>
      
    
    
      <link rel="stylesheet" href="../../assets/stylesheets/main.c4007cdc.min.css">
      
        <link rel="stylesheet" href="../../assets/stylesheets/palette.8435c73a.min.css">
      
      
        
        
        <meta name="theme-color" content="#2196f3">
      
    
    
    
      
        <link href="https://fonts.gstatic.com" rel="preconnect" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700%7CRoboto+Mono&display=fallback">
        <style>body,input{font-family:"Roboto",-apple-system,BlinkMacSystemFont,Helvetica,Arial,sans-serif}code,kbd,pre{font-family:"Roboto Mono",SFMono-Regular,Consolas,Menlo,monospace}</style>
      
    
    
    
    
      
    
    
  </head>
  
  
    
    
    <body dir="" data-md-color-primary="blue" data-md-color-accent="blue">
  
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" for="__drawer"></label>
    <div data-md-component="skip">
      
        
        <a href="#_1" class="md-skip">
          跳转至
        </a>
      
    </div>
    <div data-md-component="announce">
      
    </div>
    
      <header class="md-header" data-md-component="header">
  <nav class="md-header-nav md-grid" aria-label="">
    <a href="../.." title="操作系统（2020秋季） | 哈工大（深圳）" class="md-header-nav__button md-logo" aria-label="操作系统（2020秋季） | 哈工大（深圳）">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path d="M416 48v416c0 26.51-21.49 48-48 48H144c-26.51 0-48-21.49-48-48V48c0-26.51 21.49-48 48-48h224c26.51 0 48 21.49 48 48zm96 58v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42V88h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zM30 376h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6z"/></svg>

    </a>
    <label class="md-header-nav__button md-icon" for="__drawer">
      <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M3 6h18v2H3V6m0 5h18v2H3v-2m0 5h18v2H3v-2z"/></svg>
    </label>
    <div class="md-header-nav__title" data-md-component="header-title">
      
        <div class="md-header-nav__ellipsis">
          <span class="md-header-nav__topic md-ellipsis">
            操作系统（2020秋季） | 哈工大（深圳）
          </span>
          <span class="md-header-nav__topic md-ellipsis">
            
              实验概述
            
          </span>
        </div>
      
    </div>
    
      <label class="md-header-nav__button md-icon" for="__search">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M9.5 3A6.5 6.5 0 0116 9.5c0 1.61-.59 3.09-1.56 4.23l.27.27h.79l5 5-1.5 1.5-5-5v-.79l-.27-.27A6.516 6.516 0 019.5 16 6.5 6.5 0 013 9.5 6.5 6.5 0 019.5 3m0 2C7 5 5 7 5 9.5S7 14 9.5 14 14 12 14 9.5 12 5 9.5 5z"/></svg>
      </label>
      
<div class="md-search" data-md-component="search" role="dialog">
  <label class="md-search__overlay" for="__search"></label>
  <div class="md-search__inner" role="search">
    <form class="md-search__form" name="search">
      <input type="text" class="md-search__input" name="query" aria-label="搜索" placeholder="搜索" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="search-query" data-md-state="active">
      <label class="md-search__icon md-icon" for="__search">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M9.5 3A6.5 6.5 0 0116 9.5c0 1.61-.59 3.09-1.56 4.23l.27.27h.79l5 5-1.5 1.5-5-5v-.79l-.27-.27A6.516 6.516 0 019.5 16 6.5 6.5 0 013 9.5 6.5 6.5 0 019.5 3m0 2C7 5 5 7 5 9.5S7 14 9.5 14 14 12 14 9.5 12 5 9.5 5z"/></svg>
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
      </label>
      <button type="reset" class="md-search__icon md-icon" aria-label="" data-md-component="search-reset" tabindex="-1">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M19 6.41L17.59 5 12 10.59 6.41 5 5 6.41 10.59 12 5 17.59 6.41 19 12 13.41 17.59 19 19 17.59 13.41 12 19 6.41z"/></svg>
      </button>
    </form>
    <div class="md-search__output">
      <div class="md-search__scrollwrap" data-md-scrollfix>
        <div class="md-search-result" data-md-component="search-result">
          <div class="md-search-result__meta">
            
          </div>
          <ol class="md-search-result__list"></ol>
        </div>
      </div>
    </div>
  </div>
</div>
    
    
      <div class="md-header-nav__source">
        
<a href="https://gitee.com/hitsz-lab/os_lab" title="前往 GitHub 仓库" class="md-source">
  <div class="md-source__icon md-icon">
    
    <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><path d="M439.55 236.05L244 40.45a28.87 28.87 0 00-40.81 0l-40.66 40.63 51.52 51.52c27.06-9.14 52.68 16.77 43.39 43.68l49.66 49.66c34.23-11.8 61.18 31 35.47 56.69-26.49 26.49-70.21-2.87-56-37.34L240.22 199v121.85c25.3 12.54 22.26 41.85 9.08 55a34.34 34.34 0 01-48.55 0c-17.57-17.6-11.07-46.91 11.25-56v-123c-20.8-8.51-24.6-30.74-18.64-45L142.57 101 8.45 235.14a28.86 28.86 0 000 40.81l195.61 195.6a28.86 28.86 0 0040.8 0l194.69-194.69a28.86 28.86 0 000-40.81z"/></svg>
  </div>
  <div class="md-source__repository">
    HITSZ-OS-Course
  </div>
</a>
      </div>
    
  </nav>
</header>
    
    <div class="md-container" data-md-component="container">
      
        
      
      
        
          

  

<nav class="md-tabs md-tabs--active" aria-label="" data-md-component="tabs">
  <div class="md-tabs__inner md-grid">
    <ul class="md-tabs__list">
      
        
  <li class="md-tabs__item">
    
      <a href="../.." class="md-tabs__link">
        实验须知
      </a>
    
  </li>

      
        
      
        
      
        
      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../lab1/part1/" class="md-tabs__link">
          Lab1：xv6与Unix实用程序
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../lab2/part1/" class="md-tabs__link">
          Lab2：实现一个简单的shell
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="./" class="md-tabs__link md-tabs__link--active">
          Lab3：锁机制的应用
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../lab4/part1/" class="md-tabs__link">
          Lab4：内存管理之伙伴系统
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../lab5/part1/" class="md-tabs__link">
          Lab5：简单文件系统的设计与实现
        </a>
      
    </li>
  

      
    </ul>
  </div>
</nav>
        
      
      <main class="md-main" data-md-component="main">
        <div class="md-main__inner md-grid">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="navigation">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    <nav class="md-nav md-nav--primary" aria-label="" data-md-level="0">
  <label class="md-nav__title" for="__drawer">
    <a href="../.." title="操作系统（2020秋季） | 哈工大（深圳）" class="md-nav__button md-logo" aria-label="操作系统（2020秋季） | 哈工大（深圳）">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path d="M416 48v416c0 26.51-21.49 48-48 48H144c-26.51 0-48-21.49-48-48V48c0-26.51 21.49-48 48-48h224c26.51 0 48 21.49 48 48zm96 58v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42V88h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zM30 376h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6z"/></svg>

    </a>
    操作系统（2020秋季） | 哈工大（深圳）
  </label>
  
    <div class="md-nav__source">
      
<a href="https://gitee.com/hitsz-lab/os_lab" title="前往 GitHub 仓库" class="md-source">
  <div class="md-source__icon md-icon">
    
    <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><path d="M439.55 236.05L244 40.45a28.87 28.87 0 00-40.81 0l-40.66 40.63 51.52 51.52c27.06-9.14 52.68 16.77 43.39 43.68l49.66 49.66c34.23-11.8 61.18 31 35.47 56.69-26.49 26.49-70.21-2.87-56-37.34L240.22 199v121.85c25.3 12.54 22.26 41.85 9.08 55a34.34 34.34 0 01-48.55 0c-17.57-17.6-11.07-46.91 11.25-56v-123c-20.8-8.51-24.6-30.74-18.64-45L142.57 101 8.45 235.14a28.86 28.86 0 000 40.81l195.61 195.6a28.86 28.86 0 0040.8 0l194.69-194.69a28.86 28.86 0 000-40.81z"/></svg>
  </div>
  <div class="md-source__repository">
    HITSZ-OS-Course
  </div>
</a>
    </div>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
      
      


  <li class="md-nav__item">
    <a href="../.." title="实验须知" class="md-nav__link">
      实验须知
    </a>
  </li>

    
      
      
      


  <li class="md-nav__item">
    <a href="../../env/" title="实验平台以及环境配置" class="md-nav__link">
      实验平台以及环境配置
    </a>
  </li>

    
      
      
      


  <li class="md-nav__item">
    <a href="../../Linux/" title="Linux开发环境基础知识" class="md-nav__link">
      Linux开发环境基础知识
    </a>
  </li>

    
      
      
      


  <li class="md-nav__item">
    <a href="../../remote_env/" title="远程实验环境使用指南" class="md-nav__link">
      远程实验环境使用指南
    </a>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-5" type="checkbox" id="nav-5">
    
    <label class="md-nav__link" for="nav-5">
      Lab1：xv6与Unix实用程序
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab1：xv6与Unix实用程序" data-md-level="1">
      <label class="md-nav__title" for="nav-5">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab1：xv6与Unix实用程序
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab1/part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab1/part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab1/part3/" title="实验步骤" class="md-nav__link">
      实验步骤
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab1/part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-6" type="checkbox" id="nav-6">
    
    <label class="md-nav__link" for="nav-6">
      Lab2：实现一个简单的shell
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab2：实现一个简单的shell" data-md-level="1">
      <label class="md-nav__title" for="nav-6">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab2：实现一个简单的shell
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab2/part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab2/part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab2/part3/" title="实验提示" class="md-nav__link">
      实验提示
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab2/part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      

  


  <li class="md-nav__item md-nav__item--active md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-7" type="checkbox" id="nav-7" checked>
    
    <label class="md-nav__link" for="nav-7">
      Lab3：锁机制的应用
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab3：锁机制的应用" data-md-level="1">
      <label class="md-nav__title" for="nav-7">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab3：锁机制的应用
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          

  


  <li class="md-nav__item md-nav__item--active">
    
    <input class="md-nav__toggle md-toggle" data-md-toggle="toc" type="checkbox" id="__toc">
    
      
    
    
      <label class="md-nav__link md-nav__link--active" for="__toc">
        实验概述
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M3 9h14V7H3v2m0 4h14v-2H3v2m0 4h14v-2H3v2m16 0h2v-2h-2v2m0-10v2h2V7h-2m0 6h2v-2h-2v2z"/></svg>
        </span>
      </label>
    
    <a href="./" title="实验概述" class="md-nav__link md-nav__link--active">
      实验概述
    </a>
    
      
<nav class="md-nav md-nav--secondary" aria-label="目录">
  
  
    
  
  
    <label class="md-nav__title" for="__toc">
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
      </span>
      目录
    </label>
    <ul class="md-nav__list" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#1" class="md-nav__link">
    1.  实验目的
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#2" class="md-nav__link">
    2.  实验学时
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#3" class="md-nav__link">
    3.  实验内容及要求
  </a>
  
    <nav class="md-nav" aria-label="3.  实验内容及要求">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#31-memory-allocator" class="md-nav__link">
    3.1 任务一：内存分配器（Memory allocator）
  </a>
  
    <nav class="md-nav" aria-label="3.1 任务一：内存分配器（Memory allocator）">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#311-kalloctest" class="md-nav__link">
    3.1.1 关于测评程序kalloctest
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#312" class="md-nav__link">
    3.1.2 具体要求
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#313" class="md-nav__link">
    3.1.3 提示
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
        
          <li class="md-nav__item">
  <a href="#32-buffer-cache" class="md-nav__link">
    3.2 任务二：磁盘缓存（Buffer cache）
  </a>
  
    <nav class="md-nav" aria-label="3.2 任务二：磁盘缓存（Buffer cache）">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#321-bcachetest" class="md-nav__link">
    3.2.1 关于测评程序bcachetest
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#322" class="md-nav__link">
    3.2.2 具体要求
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#323" class="md-nav__link">
    3.2.3 提示
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
        
          <li class="md-nav__item">
  <a href="#33" class="md-nav__link">
    3.3 测评
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
    </ul>
  
</nav>
    
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../part3/" title="实验步骤" class="md-nav__link">
      实验步骤
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-8" type="checkbox" id="nav-8">
    
    <label class="md-nav__link" for="nav-8">
      Lab4：内存管理之伙伴系统
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab4：内存管理之伙伴系统" data-md-level="1">
      <label class="md-nav__title" for="nav-8">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab4：内存管理之伙伴系统
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab4/part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab4/part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab4/part3/" title="实验步骤" class="md-nav__link">
      实验步骤
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab4/part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-9" type="checkbox" id="nav-9">
    
    <label class="md-nav__link" for="nav-9">
      Lab5：简单文件系统的设计与实现
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab5：简单文件系统的设计与实现" data-md-level="1">
      <label class="md-nav__title" for="nav-9">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab5：简单文件系统的设计与实现
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab5/part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab5/part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab5/part3/" title="实验要求" class="md-nav__link">
      实验要求
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab5/part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
              <div class="md-sidebar md-sidebar--secondary" data-md-component="toc">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    
<nav class="md-nav md-nav--secondary" aria-label="目录">
  
  
    
  
  
    <label class="md-nav__title" for="__toc">
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
      </span>
      目录
    </label>
    <ul class="md-nav__list" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#1" class="md-nav__link">
    1.  实验目的
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#2" class="md-nav__link">
    2.  实验学时
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#3" class="md-nav__link">
    3.  实验内容及要求
  </a>
  
    <nav class="md-nav" aria-label="3.  实验内容及要求">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#31-memory-allocator" class="md-nav__link">
    3.1 任务一：内存分配器（Memory allocator）
  </a>
  
    <nav class="md-nav" aria-label="3.1 任务一：内存分配器（Memory allocator）">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#311-kalloctest" class="md-nav__link">
    3.1.1 关于测评程序kalloctest
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#312" class="md-nav__link">
    3.1.2 具体要求
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#313" class="md-nav__link">
    3.1.3 提示
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
        
          <li class="md-nav__item">
  <a href="#32-buffer-cache" class="md-nav__link">
    3.2 任务二：磁盘缓存（Buffer cache）
  </a>
  
    <nav class="md-nav" aria-label="3.2 任务二：磁盘缓存（Buffer cache）">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#321-bcachetest" class="md-nav__link">
    3.2.1 关于测评程序bcachetest
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#322" class="md-nav__link">
    3.2.2 具体要求
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#323" class="md-nav__link">
    3.2.3 提示
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
        
          <li class="md-nav__item">
  <a href="#33" class="md-nav__link">
    3.3 测评
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
    </ul>
  
</nav>
                  </div>
                </div>
              </div>
            
          
          <div class="md-content">
            <article class="md-content__inner md-typeset">
              
                
                
                  
                
                
                <h1 id="_1">实验概述</h1>
<h2 id="1">1.  实验目的</h2>
<ol>
<li>了解Lock的实现原理，理解CPU为Lock的实现提供的支持。</li>
<li>理解xv6的内存分配器kalloc以及磁盘缓存buffer cache的工作原理，掌握Lock在xv6中内存分配器/磁盘缓存中的作用。</li>
<li>掌握锁竞争对程序并行性的影响。</li>
<li>学习减少锁竞争的方法。</li>
</ol>
<h2 id="2">2.  实验学时</h2>
<p>本实验为4学时。</p>
<h2 id="3">3.  实验内容及要求</h2>
<p>实验开始前， <strong>请切换到lock分支</strong> </p>
<p><img alt="image-20201121102002363" src="../part1.assets/image-20201121102002363.png" /></p>
<p>多核计算机上并行性差的一个常见症状是高锁争用。为了减少争用，提高并行性通常需要同时改变数据结构和锁定策略。在这个实验中，我们需要为xv6内存分配器和磁盘缓存buffer cache重新设计代码提高并行性。</p>
<p>​    本实验内容详见MIT官方指导：</p>
<p>​    <a href="https://pdos.csail.mit.edu/6.828/2019/labs/lock.html">https://pdos.csail.mit.edu/6.828/2019/labs/lock.html</a></p>
<h3 id="31-memory-allocator">3.1 任务一：内存分配器（Memory allocator）</h3>
<p>修改空闲内存列表管理机制，使每个CPU核使用独立的列表，而不是现在的共享列表；同时，支持在当前CPU的空闲链表（free list ）为空，其他链表不为空的情况下，可以从其他CPU的空闲链表中窃取（steal）空闲内存，从而减少列表操作时的锁争用。运行测评程序kalloctest，查看是否减少锁争用，并检查它是否仍然可用分配所有内存。</p>
<h4 id="311-kalloctest">3.1.1 关于测评程序kalloctest</h4>
<p>测评程序kalloctest（见user/kalloctest.c）的测试方式如下：</p>
<p>该测评程序通过频繁调用sbrk分配或释放连续的4KB内存空间，导致kalloc和kfree（见kernel/kalloc.c）也频繁被调用，而kalloc和kfree每次分配和释放内存空间都需要获取kmen.lock锁。</p>
<p>以下代码来自user/kalloctest.c</p>
<p><img alt="image-20201121105757091" src="../part1.assets/image-20201121105757091.png" /></p>
<div class="highlight"><pre><span></span><code>关于sbrk()系统调用

文件位置：kernel/sysproc.c。作用：为进程分配或回收内存。
它有一个参数，代表要分配的字节数。它返回的是新分配内存的地址。

这个系统调用是通过growproc来实现的。
如果给的参数是正数，growproc使用uvmalloc(kernel/vm.c:236) 来分配内存。
如果给的参数是负数，使用uvmdealloc来释放内存。

uvmalloc首先使用kalloc来分配物理内存，然后再用mappages把PTE加到用户的页表里。
uvmdealloc调用uvmunmap(kernel/vm.c:176)实现其功能，
uvmunmap首先用walk来找到对应的PTE，然后使用kfree来释放相应的物理内存。
</code></pre></div>

<p>测评程序kalloctest最终会打印出test-and-sets的数目，也就是没有成功获取到kmem锁的次数，这种粗略测量锁争用的方式（实验前，即未修改前）如下：</p>
<p><img alt="image-20201121105931197" src="../part1.assets/image-20201121105931197.png" /></p>
<p>其中，acquire()记录了每种锁调用acquire()函数的次数，test-and-sets就是没有获取到此锁的次数。kalloctest调用一个系统调用ntas()，使内核打印那些针对kmem和bcache锁(本实验的重点)及5个竞争最激烈的锁的计数。如果存在锁争用，test-and-sets的数量将会很高，因为在acquire()获得锁之前需要进行许多循环迭代，系统调用会返回kmem和bcache锁的#test-and-set的总和。</p>
<p>kalloctest中锁争用的根本原因是kalloc()中只有被单一的kmen.lock锁保存的一个单独的空闲链表。为了消除锁竞争，需要重新设计内存分配器来避免单一的锁和单一的链表。 <strong>本实验基本的思路就是为每个CPU维护一个空闲链表，每个链表有专用的锁。</strong> 不同CPU上的内存分配器可以并行运行，因为每次CPU会操作不同的空闲链表。本实验中主要的挑战是，当一个CPU的空闲链表为空（即没有空闲链表），其他CPU有空闲内存时，在这种情况下，该CPU可以从其他CPU的空闲链表窃取（steal）内存。窃取内存（steal）操作也许会引入锁竞争，但由于它不会很频繁，是容许的。</p>
<h4 id="312">3.1.2 具体要求</h4>
<p>1)   本实验必须使用多核的环境，否则数据将没有意义；</p>
<p>2)   请使用initlock()初始化锁，并要求锁名字以kmem开头；</p>
<p>3)   运行kalloctest查看实现的代码是否减少了锁争用（#test-and-set 没有获取到此锁的次数小于10则为通过），并确认它可以分配所有的内存；</p>
<p>4)   实现的代码不得影响xv6的基本功能，所以请确保usertests能够全部通过；</p>
<p>5)   Kalloctest和usertests的输出如下图，具体的数据会有所差别：</p>
<p><img alt="image-20201121113349405" src="../part1.assets/image-20201121113349405.png" /></p>
<h4 id="313">3.1.3 提示</h4>
<p>1)   可以使用kernel/param.h中的宏NCPU；</p>
<p>2)   使用freerange为所有运行freerange的CPU分配空闲的内存；</p>
<p>3)   函数cpuid()可以返回当前核的编号，但是该函数只有在中断关闭时调用才是安全的，因此请在使用前后分别调用push_off()和pop_off()来关闭和恢复中断。</p>
<h3 id="32-buffer-cache">3.2 任务二：磁盘缓存（Buffer cache）</h3>
<p>如果有多进程密集地使用文件系统，他们可能会竞争bcache.lock锁，该锁用于保护磁盘数据在内存的缓存块（见kernel/bio.c）。修改磁盘缓存块列表的管理机制，建立缓存块和锁的哈希映射，使得可用多个锁管理缓存块，从而减少缓存块管理的锁争用。</p>
<h4 id="321-bcachetest">3.2.1 关于测评程序bcachetest</h4>
<p>测评程序bcachetest（见user/bcachetest.c）的测试方式如下：</p>
<p>创建多个进程重复去读取不同的文件，从而造成bcache.lock锁争用。</p>
<p>实验前（即未修改前），测评程序bcachetest的输出如下：</p>
<p><img alt="image-20201121115145621" src="../part1.assets/image-20201121115145621.png" /></p>
<p>当然，图中的具体数据并非每次完全一致，但是可以看出来bcache.lock锁test-and-set的次数很高。查阅kernel/bio.c代码可知，bcache.lock锁用于保护磁盘缓冲数据块的链表、每个缓存数据块的引用计数b-&gt;refcnt、以及缓存数据块的b-&gt;dev、 b-&gt;blockno等。</p>
<p>请修改buffer cache的设计，使得使用测评程序bcachetest时，所有锁的test-and-set的数目接近于0。</p>
<p>在kernel/bio.c中，可以看到，所有的buffer都被组织到一条链表中，因此如果有多个进程要使用buffer，它们并发的请求只能被顺序地处理。</p>
<p>减少缓存数据块的锁争用会比kalloc的锁争用处理更加刺手，因为缓存数据块本身是在多个进程间（或者说多个CPU间）共享的。对于kalloc来说，为每个CPU分配独有的内存分配器空闲链表就可以消除大多数的锁。要降低锁争用使用类似kalloc的方案，对于缓存数据块（buffer cache）来说并不合适。</p>
<div class="highlight"><pre><span></span><code>MIT官方指导书推荐使用以下两种方案（可以两个方案一起使用，也可以单独分开使用，
需要自行测试看看能否通过测评程序） ：

（1）使用哈希表将各个块按块号blockno作为key分组，并为每个组分配一个专用的锁。
在bget()中查找指定块时，锁上对应的锁（获取空闲块号须另作处理）。
分组的数量不必动态调整，可以取定值，推荐使用质数组（如13组）以减少哈希争用。
哈希表的搜索和空闲缓存块的查找需要保证原子性。

（2）移除空闲缓存块列表(bcache.head)。使用时间戳作为判断缓存块最后一次被访问的顺序的依据。
此项改动可使brelse不再需要锁上bcache lock，
bget在找空闲块时也可通过时间戳得知最后一次被访问时间最早的空闲缓存块。
时间戳可通过kernel/trap.c中的ticks获得（ticks已在kernel/def.h中声明，bio.c中可直接使用）。
</code></pre></div>

<p>以下情况中，锁争用是允许的：</p>
<p>a)   当两个进程同时访问同一个缓存数据块号blockno时；</p>
<p>b)   当两个进程同时没有命中cache，需要找一个未使用的block来替代时；</p>
<p>c)   当两个进程同时使用无论使用何种模式划分数据块和锁都会争用的块时，比如，如果两个进程使用的两个数据块，通过哈希表映射到同一个哈希组部分取决于具体的设计，请尝试调整具体的模式来避免争用，比如可以调整哈希表的大小。</p>
<h4 id="322">3.2.2 具体要求</h4>
<p>1)   请将本实验涉及的锁以“bcache”开头来命名，可以调用initlock()来初始化bcache锁；</p>
<p>2)   理想状态下，bcachetest中数据块缓存相关的所有锁test-and-set的总和应该为0，但本实验中总和不超过500即可；</p>
<p>3)   请修改bget()和brelse()，使得缓存区并发的查询和释放不容易发生锁争用，比如，不是所有流程都得等bcache.lock；</p>
<p>4)   每个数据块最多只能维护一份缓存；</p>
<p>5)   同样要求usertests中的用例全部通过，最后的输出如下（具体数据有所出入）：</p>
<p><img alt="image-20201121122717579" src="../part1.assets/image-20201121122717579.png" /></p>
<h4 id="323">3.2.3 提示</h4>
<p>1)   请阅读xv6 book中7.2 - 7.3 节关于块缓存的描述；</p>
<p>2)   哈希组的数目可以使用固定的数目，不需要动态地扩展哈希表的大小。请使用素数（比如13）来定义哈希组的数目来尽可能减少哈希争用；</p>
<p>3)   在哈希表中搜索块缓存且为未命中的缓存分配一个新的条目，这整个操作必须是原子性操作的；</p>
<p>4)   允许序列化（按顺序）查找未被使用的数据缓存块（即引用计数refcnt为0），也就是说当bget()查找数据块未命中时，bget可以选择一个这样的未被使用的缓存块，移入到以blockno为key的哈希组链表中使用。</p>
<p>5)   如果您的实现中出现了同时锁上两个以上的锁的情况（比如说，bget()在获取空闲块时，需要移动一个内存块从一个哈希组到另一个哈希组），注意避免死锁的出现。</p>
<h3 id="33">3.3 测评</h3>
<p>当完成上述两项任务后，使用make grade命令，确认所有测试已通过。</p>
<p>make grade的time: FAIL可以不做理会，分数达到99分即为通过。下图视为通过测试：</p>
<p><img alt="make_grade_pass" src="../part1.assets/make_grade_pass.jpg" /></p>
                
              
              
                


              
            </article>
          </div>
        </div>
      </main>
      
        
<footer class="md-footer">
  
    <div class="md-footer-nav">
      <nav class="md-footer-nav__inner md-grid" aria-label="">
        
          <a href="../../lab2/part4/" title="提交文档" class="md-footer-nav__link md-footer-nav__link--prev" rel="prev">
            <div class="md-footer-nav__button md-icon">
              <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
            </div>
            <div class="md-footer-nav__title">
              <div class="md-ellipsis">
                <span class="md-footer-nav__direction">
                  上一页
                </span>
                提交文档
              </div>
            </div>
          </a>
        
        
          <a href="../part2/" title="实验原理" class="md-footer-nav__link md-footer-nav__link--next" rel="next">
            <div class="md-footer-nav__title">
              <div class="md-ellipsis">
                <span class="md-footer-nav__direction">
                  下一页
                </span>
                实验原理
              </div>
            </div>
            <div class="md-footer-nav__button md-icon">
              <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M4 11v2h12l-5.5 5.5 1.42 1.42L19.84 12l-7.92-7.92L10.5 5.5 16 11H4z"/></svg>
            </div>
          </a>
        
      </nav>
    </div>
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-footer-copyright">
        
          <div class="md-footer-copyright__highlight">
            Copyright &copy; 2020 - 2021 哈尔滨工业大学（深圳）
          </div>
        
        Made with
        <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
          Material for MkDocs
        </a>
      </div>
      
    </div>
  </div>
</footer>
      
    </div>
    
      <script src="../../assets/javascripts/vendor.83fe6e3c.min.js"></script>
      <script src="../../assets/javascripts/bundle.7e1cb91c.min.js"></script><script id="__lang" type="application/json">{"clipboard.copy": "\u590d\u5236", "clipboard.copied": "\u5df2\u590d\u5236", "search.config.lang": "ja", "search.config.pipeline": "", "search.config.separator": "[\\uff0c\\u3002]+", "search.result.placeholder": "\u952e\u5165\u4ee5\u5f00\u59cb\u641c\u7d22", "search.result.none": "\u6ca1\u6709\u627e\u5230\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.one": "\u627e\u5230 1 \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.other": "# \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c"}</script>
      
      <script>
        app = initialize({
          base: "../..",
          features: ["tabs"],
          search: Object.assign({
            worker: "../../assets/javascripts/worker/search.37585f48.min.js"
          }, typeof search !== "undefined" && search)
        })
      </script>
      
        <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML"></script>
      
    
  </body>
</html>